package bintree.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author yuisama
 * @date 2023年07月13日 15:07
 * @description 回溯之 -- 二叉树中和为某一值的路径
 */
public class Offer34_PathSum {
    // 记录走过的路径
    LinkedList<Integer> path = new LinkedList<>();
    // 记录满足条件的解
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        pathHelper(root,target);
        return res;
    }
    // 从当前节点出发，寻找和为target的节点路径
    private void pathHelper(TreeNode root, int target) {
        // base case
        if (root == null) {
            return;
        }
        // 做出选择
        path.add(root.val);
        target -= root.val;
        // 当前节点添加后是否是一个解
        if (target == 0 && root.left == null && root.right == null) {
            // 注意，此处要创建一个新的副本List，否则其他的操作会影响结果集
            res.add(new LinkedList<>(path));
        }
        // 继续递归选择
        pathHelper(root.left,target);
        pathHelper(root.right,target);
        // 以当前root为根的树访问结束后，撤销选择
        path.removeLast();
    }
}
